package letcode.problem.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    private int[] arr;

    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    public void sort() {
        /**
         * 1. 将数组堆化
         * */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1;
        for (int i = beginIndex; i >= 0; i--) {
            maxHeapify(i, len);
        }

        for (int i = len; i > 0; i--) {
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整索引为index处的数据，使其符合堆的特性
     *
     * @param index 需要堆化处理数据的索引
     * @param len   未排序堆的长度
     */
    private void maxHeapify(int index, int len) {
        int li = (index << 1) + 1;//左子节点索引
        int ri = li + 1;//右子节点索引
        int cMax = li;//子节点最大索引 默认为左子节点
        if (li > len) return;
        if (ri <= len && arr[ri] > arr[li]) {
            cMax = ri;
        }
        if (arr[cMax] > arr[index]) {
            swap(cMax, index);
            maxHeapify(cMax, len);
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
        new HeapSort(arr).sort();
        System.out.println(Arrays.toString(arr));
    }

}
